package me.sealer.algorithm.sort;

/**
 * Created by sealer on 17/02/26.
 */
public class Insert {

    /**
     * 插入排序
     * <p>
     * 从第一个元素开始，该元素可以认为已经被排序
     * 取出下一个元素，在已经排序的元素序列中从后向前扫描
     * 如果该元素（已排序）大于新元素，将该元素移到下一位置
     * 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
     * 将新元素插入到该位置中
     * 重复步骤2
     *
     * @param numbers 待排序数组s
     */
    public static void sort(int[] numbers) {
        int size = numbers.length;
        int temp;//暂存待插入的值
        int j;

        for (int i = 1; i < size; i++) {
            temp = numbers[i];
            for (j = i; j > 0 && temp < numbers[j - 1]; j--) {
                //假如temp比前面的值小，则将前面的值后移
                numbers[j] = numbers[j - 1];
            }

            numbers[j] = temp;
        }
    }

    /**
     * 二分查找选择排序
     *
     * @param numbers
     */
    public static void binaryInsertSort(int[] numbers) {
        int size = numbers.length;
        int temp;

        for (int i = 1; i < size; i++) {
            temp = numbers[i];
            int low = 0, high = i - 1, mid;
            while (low <= high) {
                mid = (low + high) >>> 1;//无符号右移一位， 相当于除以2
                if (temp < numbers[mid]) {
                    high = mid - 1;
                } else {
                    low = mid + 1;
                }
            }
            for (int j = i - 1; j >= low; j--) {
                numbers[j + 1] = numbers[j];
            }

            numbers[low] = temp;
        }

    }
}
